{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Average Subarray II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaxAverage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组最大平均数 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个包含 <code>n</code> 个整数的数组 <code>nums</code> ，和一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请你找出<strong> 长度大于等于</strong> <code>k</code> 且含最大平均值的连续子数组。并输出这个最大平均值。任何计算误差小于 <code>10<sup>-5</sup></code> 的结果都将被视为正确答案。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,12,-5,-6,50,3], k = 4\n",
    "<strong>输出：</strong>12.75000\n",
    "<strong>解释：\n",
    "</strong>- 当长度为 4 的时候，连续子数组平均值分别为 [0.5, 12.75, 10.5] ，其中最大平均值是 12.75 。\n",
    "- 当长度为 5 的时候，连续子数组平均值分别为 [10.4, 10.8] ，其中最大平均值是 10.8 。\n",
    "- 当长度为 6 的时候，连续子数组平均值分别为 [9.16667] ，其中最大平均值是 9.16667 。\n",
    "当取长度为 4 的子数组（即，子数组 [12, -5, -6, 50]）的时候，可以得到最大的连续子数组平均值 12.75 ，所以返回 12.75 。\n",
    "根据题目要求，无需考虑长度小于 4 的子数组。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5], k = 1\n",
    "<strong>输出：</strong>5.00000\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 <= k <= n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-average-subarray-ii](https://leetcode.cn/problems/maximum-average-subarray-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-average-subarray-ii](https://leetcode.cn/problems/maximum-average-subarray-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,12,-5,-6,50,3]\\n4', '[5]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        size = len(nums)\n",
    "        res = -float('inf')\n",
    "        total = 0\n",
    "        res = -float('inf')\n",
    "        for index, n in enumerate(nums):\n",
    "            if index <= k - 1:\n",
    "                total += n\n",
    "                if index == k - 1:\n",
    "                    res = max(total/k, res)\n",
    "            else:\n",
    "                total = total-nums[index-k] + nums[index]\n",
    "                res = max(total/k, res)\n",
    "  \n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        l = len(nums)\n",
    "        if k == 1: return max(nums)\n",
    "        if k== l:  return sum(nums) / k\n",
    "        sums = maxs = sum(nums[0:k]) # 0 1 2 \n",
    "        for i in range(k,l):\n",
    "            sums = sums + nums[i] - nums[i-k]\n",
    "            maxs = max(sums,maxs)\n",
    "                \n",
    "        return maxs/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        res = sum(nums[0:k])\n",
    "        temp = res;\n",
    "        n = len(nums)\n",
    "        for i in range(k,n):\n",
    "            res = res - nums[i-k] + nums[i]\n",
    "            temp = max(temp,res)\n",
    "            \n",
    "        return temp/(k+0.0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        min_nums = 0\n",
    "        pre_sum = 0\n",
    "        for j in range(k):\n",
    "            min_nums+=nums[j]\n",
    "        \n",
    "        pre_sum = min_nums\n",
    "        \n",
    "        for i in range(k,len(nums)):\n",
    "            \n",
    "            now = pre_sum + nums[i] - nums[i-k]\n",
    "            if min_nums <now:\n",
    "                min_nums = now\n",
    "            pre_sum = now\n",
    "            \n",
    "        return min_nums/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        s = sum(nums[:k])\n",
    "        r = s\n",
    "        for i in range(k, len(nums)):\n",
    "            s += nums[i]\n",
    "            s -= nums[i-k]\n",
    "            r = max(r, s)\n",
    "        return r/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: float\n",
    "        \"\"\"\n",
    "        nsum = [0]\n",
    "        for num in nums:\n",
    "            nsum.append(nsum[-1]+num)\n",
    "        maxsum = max(nsum[i+k]-nsum[i] for i in range(len(nums)-k+1))\n",
    "        return maxsum/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: list, k: int) -> float:\n",
    "        window = []\n",
    "        s = float('-inf')\n",
    "        for i in range(len(nums)):\n",
    "            if len(window) < k:\n",
    "                window.append(nums[i])\n",
    "            else:\n",
    "                if nums[i] >= window[0]:\n",
    "                    window.pop(0)\n",
    "                    window.append(nums[i])\n",
    "                else:\n",
    "                    s = max(sum(window) / k, s)\n",
    "                    window = nums[i-k+1:i+1]\n",
    "            if i == len(nums) - 1:\n",
    "                return max(sum(window) / k, s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: 'List[int]', k: 'int') -> 'float':\n",
    "        \n",
    "        currsum = sum(nums[:k])\n",
    "        maxsum = currsum\n",
    "        \n",
    "        for i in range(0,len(nums)-k):\n",
    "            currsum += nums[i+k] - nums[i]\n",
    "            maxsum = max(currsum,maxsum)\n",
    "        \n",
    "        return maxsum / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        out=0\n",
    "        res=0\n",
    "        for i in range(k):\n",
    "            res+=nums[i]\n",
    "        out=res\n",
    "        \n",
    "        i=k\n",
    "        while i<len(nums):\n",
    "            res=res+nums[i]-nums[i-k]\n",
    "            out =max(res,out)\n",
    "            i+=1\n",
    "            \n",
    "\n",
    "        return out/(1.00*k)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        isum, n = 0, len(nums)\n",
    "        for i in range(k):\n",
    "            isum += nums[i]\n",
    "        imax = isum\n",
    "        for i in range(k, n):\n",
    "            isum = isum + nums[i] - nums[i-k]\n",
    "            imax = max(imax, isum)\n",
    "        return float(imax) / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sumlist=[]\n",
    "        count=sum(nums[:k:])\n",
    "        if k==1:\n",
    "            return max(nums)\n",
    "        sumlist.append(count)\n",
    "        for i in range(1,len(nums)-k+1):\n",
    "            count=count-nums[i-1]+nums[i+k-1]\n",
    "            sumlist.append(count)\n",
    "        return float(max(sumlist)/k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        count=sum(nums[0:k])\n",
    "        max1=count\n",
    "        for i in range(k,len(nums)):\n",
    "            count=count-nums[i-k]+nums[i]\n",
    "            max1=max(max1,count)\n",
    "        return max1/k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        N = len(nums)\n",
    "        # 若数组长度小于长度k\n",
    "        if N < k:\n",
    "            return 0\n",
    "        dp = [-123456789] * N\n",
    "        dp[k-1] = sum(nums[:k])\n",
    "        for i in range(k, N):\n",
    "            dp[i] = dp[i - 1] + nums[i] - nums[i - k]\n",
    "        return max(dp) / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        res = 0\n",
    "        max_res = 0\n",
    "        for i in range(k):\n",
    "            res += nums[i]\n",
    "        print(\"first res is \" + str(res))\n",
    "        left, right = 0, k\n",
    "        max_res = res\n",
    "        while right < len(nums):\n",
    "            res -= nums[left]\n",
    "            res += nums[right]\n",
    "            left += 1\n",
    "            right += 1\n",
    "            print(res)\n",
    "            max_res = max(res, max_res)\n",
    "        return max_res / k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        if k == len(nums): return sum(nums) / k\n",
    "\n",
    "        res = sum(nums[0:k])\n",
    "        s = sum(nums[0:k])\n",
    "        for i in range(k, len(nums)):\n",
    "            s = s - nums[i-k] + nums[i]\n",
    "            res = max(res, s)\n",
    "        return res / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxTotal = total = sum(nums[:k])\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            total = total - nums[i - k] + nums[i]\n",
    "            maxTotal = max(maxTotal, total)\n",
    "        \n",
    "        return maxTotal / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        orsum = sum(nums[:k])\n",
    "        maxavg = orsum/k\n",
    "        if n<=k:\n",
    "            return maxavg\n",
    "        for i in range(k,n):\n",
    "            newsum = orsum + nums[i] - nums[i-k]\n",
    "            newavg = newsum/k\n",
    "            if newavg>maxavg:\n",
    "                maxavg = newavg\n",
    "            orsum = newsum\n",
    "        return maxavg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums) \n",
    "        if k>n:return sum(nums)/n\n",
    "        res=(sum(nums[:k]))/k\n",
    "        total=sum(nums[:k])\n",
    "        \n",
    "        for i in range(1,n-k+1):\n",
    "            total=total-nums[i-1]+nums[i+k-1]\n",
    "            average=total/k\n",
    "            res=max(res,average)   #注意是冒号，不是逗号\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxi = sum(nums[0:k])\n",
    "        total = maxi\n",
    "        for i in range(k, len(nums)):\n",
    "            total = total - nums[i-k] + nums[i]\n",
    "            maxi = max(maxi, total)\n",
    "        return maxi / k\n",
    "\n",
    "        # maxi = sum(nums[0:k])\n",
    "        # for i in range(k, len(nums)):\n",
    "        #     if nums[i] > nums[i-k]:\n",
    "        #         maxi = max(maxi, sum(nums[i-k+1:i+1]))\n",
    "        # return maxi / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sums = 0\n",
    "        max1 = float('-inf')\n",
    "        for i, num in enumerate(nums):\n",
    "            sums += num\n",
    "            if i >= k:\n",
    "                sums -= nums[i-k]\n",
    "            if i >= k -1 :\n",
    "                max1 = max(max1, sums/float(k))\n",
    "        return(max1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxTotal = total = sum(nums[:k])\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            total = total - nums[i - k] + nums[i]\n",
    "            maxTotal = max(maxTotal, total)\n",
    "        \n",
    "        return maxTotal / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        cusum = [0 for _ in range(n)]\n",
    "        cusum[0] = nums[0]\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            cusum[i] = nums[i] + cusum[i-1]\n",
    "            if i>=k:\n",
    "                res.append((cusum[i]-cusum[i-k])/(1.0*k))\n",
    "        res.append(cusum[k-1]/(1.0*k))\n",
    "        return max(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        res = sum(nums[:k])\n",
    "        total = res\n",
    "        nums = {i: nums[i] for i in range(len(nums))}\n",
    "        for i in range(len(nums)-k):\n",
    "            total = total-nums[i]+nums[i+k]\n",
    "            if total > res:\n",
    "                res = total\n",
    "        return res/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        res = sum(nums[:k])/k\n",
    "        total = res\n",
    "        nums = {i: nums[i] for i in range(len(nums))}\n",
    "        for i in range(len(nums)-k):\n",
    "            total = (total*k-nums[i]+nums[i+k])/k\n",
    "            if total > res:\n",
    "                res = total\n",
    "            # total = (total*k-nums[i]+nums[i+k])/k\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        if k == 1:\n",
    "            return max(nums)\n",
    "        else:\n",
    "            result = set()\n",
    "            m = sum(nums[0: k])\n",
    "            result.add(m)\n",
    "            for i in range(len(nums) - k):\n",
    "                m += nums[i + k] - nums[i]\n",
    "                result.add(m)\n",
    "        return max(result) / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        if len(nums) < k: return 0\n",
    "        m = {-1: 0}\n",
    "        for i, n in enumerate(nums):\n",
    "            m[i] = (n + m.get(i-1, 0))\n",
    "        \n",
    "        res = float('-inf')\n",
    "        for i in range(k-1, len(nums)):\n",
    "            # i = k-1 = 3\n",
    "            # i-k = 3-3 = 0\n",
    "            res = max(res, m[i] - m[i-k])\n",
    "        return res / k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        length = len(nums)\n",
    "        max_sum = sum(nums[:k])\n",
    "        curr_sum = max_sum\n",
    "        for start in range(1, length):\n",
    "            end = start + k - 1\n",
    "            if(end == length): break\n",
    "            curr_sum -= nums[start - 1]\n",
    "            curr_sum += nums[end]\n",
    "            max_sum = max(max_sum, curr_sum)\n",
    "        return max_sum / k\n",
    "\n",
    "        ''' 超出时间限制\n",
    "        end = k\n",
    "        for start in range(length):\n",
    "            end = start + k\n",
    "            if(end > length): break\n",
    "            avg = sum(nums[start:end]) / k\n",
    "            max_avg = max(max_avg, avg)\n",
    "        return max_avg\n",
    "        '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        from fractions import Fraction\n",
    "        ever = sum(nums[:k])\n",
    "\n",
    "        ret = ever / k\n",
    "        # ret = Fraction(ever, k)\n",
    "        for i in range(k, len(nums)):\n",
    "            ever -= nums[i-k]\n",
    "            ever += nums[i]\n",
    "            # ret = max(ret, Fraction(ever, k))\n",
    "            ret = max(ret, ever / k)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        left = 0\n",
    "        right = k-1\n",
    "        max_arvs = []\n",
    "        while right < len(nums):\n",
    "            if left == 0:\n",
    "                arv = sum(nums[left: right+1])/k\n",
    "                max_arvs.append(arv)\n",
    "            else:\n",
    "                arv += (nums[right] - nums[left-1]) / k\n",
    "                if nums[right] > nums[left-1]:\n",
    "                    max_arvs.append(arv)\n",
    "\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return max(max_arvs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        ave=sum(nums[:k])\n",
    "        tmp=ave\n",
    "        for i in range(len(nums)-k):\n",
    "            tmp=tmp-nums[i]+nums[i+k]\n",
    "            if tmp>ave:\n",
    "                ave=tmp\n",
    "        return ave*1.0/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxTotal = total = sum(nums[:k])\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(k, n):\n",
    "            total = total - nums[i - k] + nums[i]\n",
    "            maxTotal = max(maxTotal, total)\n",
    "        \n",
    "        return maxTotal / k\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 窗口\n",
    "        ans = -math.inf\n",
    "        count = 0\n",
    "        for i, j in enumerate(nums):\n",
    "            count += j\n",
    "            if i+1 >= k:\n",
    "                ans = max(ans, count)\n",
    "                count -= nums[i+1-k]\n",
    "        return ans/k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 先算第一个k窗口内的和，每次循环一位时减去i-k元素的值，加上i元素的值\n",
    "        cnt = 0\n",
    "        for i in range(k):\n",
    "            cnt += nums[i]\n",
    "        avgmax = cnt / k \n",
    "        for i in range(k , len(nums)):\n",
    "            cnt = cnt - nums[i-k] + nums[i]\n",
    "            avgmax = max(avgmax , cnt / k)\n",
    "        return avgmax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 用滑动窗口\n",
    "        # 定义需要维护的变量\n",
    "        maxx = float('-inf')\n",
    "        # 定义 start \n",
    "        start = 0\n",
    "        summ = 0\n",
    "        for end in range(len(nums)):\n",
    "            summ += nums[end]\n",
    "            if end - start + 1 == k:\n",
    "                # 更新\n",
    "                maxx = max(summ, maxx)\n",
    "            if end >= k-1:\n",
    "                summ -= nums[start]\n",
    "                start += 1\n",
    "        return maxx/k            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sum_, avg_max = 0, -math.inf\n",
    "        start = 0\n",
    "        for end in range(len(nums)):\n",
    "            sum_ += nums[end]\n",
    "            if end - start + 1 == k:\n",
    "                avg_max = max(avg_max, sum_ / k)\n",
    "            if end >= k -1:\n",
    "                sum_ -= nums[start]\n",
    "                start += 1\n",
    "        return avg_max "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        maxSum = curSum = sum(nums[:k])\n",
    "\n",
    "        for r in range(k, len(nums)):\n",
    "            curSum = curSum - nums[r-k] + nums[r]\n",
    "            maxSum = max(maxSum, curSum)\n",
    "        \n",
    "        return maxSum / k\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        sums = 0\n",
    "        left = 0 \n",
    "        maxavg = -math.inf\n",
    "        for right in range(len(nums)):\n",
    "            sums += nums[right] \n",
    "            if right - left + 1 == k:\n",
    "                maxavg = max(maxavg, sums / k)\n",
    "\n",
    "            if right >= k-1:\n",
    "                sums -= nums[left] \n",
    "                left +=1 \n",
    "\n",
    "        return maxavg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums, k):\n",
    "        max_val = max(nums)\n",
    "        min_val = min(nums)\n",
    "        prev_mid = max_val\n",
    "        error = float('inf')\n",
    "        while error > 0.00001:\n",
    "            mid = (max_val + min_val) / 2\n",
    "            if self.check(nums, mid, k):\n",
    "                min_val = mid\n",
    "            else:\n",
    "                max_val = mid\n",
    "            error = abs(prev_mid - mid)\n",
    "            prev_mid = mid\n",
    "        return min_val\n",
    "\n",
    "    def check(self, nums, mid, k):\n",
    "        sum_val = 0\n",
    "        prev = 0\n",
    "        min_sum = 0\n",
    "        for i in range(k):\n",
    "            sum_val += nums[i] - mid\n",
    "        if sum_val >= 0:\n",
    "            return True\n",
    "        for i in range(k, len(nums)):\n",
    "            sum_val += nums[i] - mid\n",
    "            prev += nums[i - k] - mid\n",
    "            min_sum = min(prev, min_sum)\n",
    "            if sum_val >= min_sum:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 答案误差不超过1e-5是使用二分搜索的提示，可以先确定最大平均值的范围一定在数组的最大元素和最小元素之间，然后在该区间内用二分搜索，对于每个值检查是否能找到满足平均值大于该值且长度>=k的子数组，逐步缩小最大平均值的范围，直到误差小于1e-5。对于给定一个值guess_avg找出原数组是否含有满足平均值大于该值且长度>=k的子数组的子问题，类似于滑动窗口，用 max_sum 记录前i个元素之和减去i * guess_avg的值，用min_start_sum记录某个连续子数组最小平均值, 这样若 max_sum - min_start_sum>=0则表示存在满足条件的子数组. \n",
    "        def check(guess_avg):\n",
    "            # 记录从nums[0]开始，长度>=k的平均值\n",
    "            max_sum = 0\n",
    "            for num in nums[:k]:\n",
    "                max_sum += num - guess_avg\n",
    "            # 记录遍历中nums[0:i]的平均值 （通过计算每个元素 - guess_avg后的累计和得到）\n",
    "            curr_sum = 0\n",
    "            # 记录遍历中nums[0:i]的某个连续子数组最小平均值\n",
    "            min_start_sum = 0\n",
    "            for i in range(k, len(nums)):\n",
    "                # 因为max_sum从k开始遍历，能够保证max_sum - min_start_sum始终对应某个长度>=k的连续子数组\n",
    "                # 这里分析min_start_sum初始化0的影响。如果min_start_sum是负数，代表着nums靠前部分存在大量平均值<guess_avg的小数字，则max_sum - min_start_sum相当于某个子数组能够甩掉前面小数字的包袱，达到平均值>=guess_avg\n",
    "                # 第二种情况min_start_sum继续为0。因为max_sum = sum(nums[:i]) - i * guess_avg, 正好说明avg(nums[:i])>=guess_avg，满足条件。\n",
    "                if max_sum - min_start_sum >= 0:\n",
    "                    return True\n",
    "                max_sum += nums[i] - guess_avg\n",
    "                curr_sum += nums[i - k] - guess_avg\n",
    "                min_start_sum = min(min_start_sum, curr_sum)\n",
    "            return max_sum - min_start_sum >= 0\n",
    "        \n",
    "        # 题目给出的元素范围\n",
    "        left, right = -10001, 10001\n",
    "        while right - left > 1e-5:\n",
    "            guess_avg = left + (right - left) / 2\n",
    "            if check(guess_avg): \n",
    "                # 存在符合条件的区间，其平均值>=guess_avg，下界向上收缩\n",
    "                # 由于这个题为double类型，分为[left, mid]和[mid, right]\n",
    "                left = guess_avg\n",
    "            else:\n",
    "                right = guess_avg\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l,r = min(nums),max(nums)\n",
    "        def ok(x):\n",
    "            ss1=0\n",
    "            ss0=0\n",
    "            mss0=inf\n",
    "            for i,c in enumerate(nums):\n",
    "                ss1+=c-x\n",
    "                if i-k>=0: \n",
    "                    ss0+=nums[i-k]-x\n",
    "                if i+1>=k:\n",
    "                    mss0=min(mss0, ss0)\n",
    "                    if ss1>=mss0: return True\n",
    "            return False\n",
    "                    \n",
    "        while abs(r-l)>pow(10,-5):\n",
    "            x=l+(r-l)/2\n",
    "            if ok(x):\n",
    "                l=x\n",
    "            else:\n",
    "                r=x\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        #前缀和+二分\n",
    "        def check(mid):\n",
    "            pre1,pre2,mpre=0,0,inf\n",
    "            for i in range(n):\n",
    "                pre1+=nums[i]-mid\n",
    "                #可以更新超前缀和\n",
    "                if i-k>=0:\n",
    "                    pre2+=nums[i-k]-mid\n",
    "                if i+1>=k:\n",
    "                    mpre=min(mpre,pre2)\n",
    "                    if pre1-mpre>=0:\n",
    "                        return True\n",
    "            return False\n",
    "        left,right=min(nums),max(nums)\n",
    "        n=len(nums)\n",
    "        while right-left>pow(10,-5):\n",
    "            mid=(left+right)/2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        lower_bound = min(nums)\n",
    "        upper_bound = max(nums)\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        def isValid(mid):\n",
    "            cur_sum = 0\n",
    "            prev = 0\n",
    "            min_prev_sum = 0\n",
    "\n",
    "            for i in range(k):\n",
    "                cur_sum += nums[i] - mid\n",
    "            \n",
    "            if cur_sum >= 0:\n",
    "                return True\n",
    "            \n",
    "            for i in range(k, n):\n",
    "                prev += nums[i - k] - mid\n",
    "                cur_sum += nums[i] - mid\n",
    "\n",
    "                min_prev_sum = min(min_prev_sum, prev)\n",
    "\n",
    "                if cur_sum >= min_prev_sum:\n",
    "                    return True\n",
    "            \n",
    "            return False\n",
    "\n",
    "        while abs(upper_bound - lower_bound) > 1e-5:\n",
    "            #print(lower_bound, upper_bound)\n",
    "            mid = lower_bound + (upper_bound - lower_bound) / 2\n",
    "\n",
    "            if isValid(mid):\n",
    "                lower_bound = mid\n",
    "            else:\n",
    "                upper_bound = mid\n",
    "        \n",
    "        print(upper_bound, lower_bound)\n",
    "        if isValid(upper_bound):\n",
    "            return upper_bound\n",
    "        \n",
    "        return lower_bound\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 答案误差不超过1e-5是使用二分搜索的提示，可以先确定最大平均值的范围一定在数组的最大元素和最小元素之间，然后在该区间内用二分搜索，对于每个值检查是否能找到满足平均值大于该值且长度>=k的子数组，逐步缩小最大平均值的范围，直到误差小于1e-5。对于给定一个值guess_avg找出原数组是否含有满足平均值大于该值且长度>=k的子数组的子问题，类似于滑动窗口，用 max_sum 记录前i个元素之和减去i * guess_avg的值，用min_start_sum记录某个连续子数组最小平均值, 这样若 max_sum - min_start_sum>=0则表示存在满足条件的子数组. \n",
    "        def check(guess_avg):\n",
    "            # 记录从nums[0]开始，长度>=k的平均值\n",
    "            max_sum = 0\n",
    "            for num in nums[:k]:\n",
    "                max_sum += num - guess_avg\n",
    "            # 记录遍历中nums[0:i]的平均值 （通过计算每个元素 - guess_avg后的累计和得到）\n",
    "            curr_sum = 0\n",
    "            # 记录遍历中nums[0:i]的某个连续子数组最小平均值\n",
    "            min_start_sum = 0\n",
    "            for i in range(k, len(nums)):\n",
    "                # 因为max_sum从k开始遍历，能够保证max_sum - min_start_sum始终对应某个长度>=k的连续子数组\n",
    "                # 这里分析min_start_sum初始化0的影响。如果min_start_sum是负数，代表着nums靠前部分存在大量平均值<guess_avg的小数字，则max_sum - min_start_sum相当于某个子数组能够甩掉前面小数字的包袱，达到平均值>=guess_avg\n",
    "                # 第二种情况min_start_sum继续为0。因为max_sum = sum(nums[:i]) - i * guess_avg, 正好说明avg(nums[:i])>=guess_avg，满足条件。\n",
    "                if max_sum - min_start_sum >= 0:\n",
    "                    return True\n",
    "                max_sum += nums[i] - guess_avg\n",
    "                curr_sum += nums[i - k] - guess_avg\n",
    "                min_start_sum = min(min_start_sum, curr_sum)\n",
    "            return max_sum - min_start_sum >= 0\n",
    "        \n",
    "        # 题目给出的元素范围\n",
    "        left, right = -10001, 10001\n",
    "        while right - left > 1e-5:\n",
    "            guess_avg = left + (right - left) / 2\n",
    "            if check(guess_avg): \n",
    "                # 存在符合条件的区间，其平均值>=guess_avg，下界向上收缩\n",
    "                # 由于这个题为double类型，分为[left, mid]和[mid, right]\n",
    "                left = guess_avg\n",
    "            else:\n",
    "                right = guess_avg\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        i, j = min(nums), max(nums)\n",
    "        def check(m: float, k: int) -> bool:\n",
    "            cumsum, prev, minsum = 0, 0, 0\n",
    "            for i in range(k):\n",
    "                cumsum += nums[i] - m\n",
    "            if cumsum >= 0:\n",
    "                return True\n",
    "            for i in range(k, len(nums)):\n",
    "                cumsum += nums[i] - m\n",
    "                prev += nums[i-k] - m\n",
    "                minsum = min(minsum, prev)\n",
    "                if cumsum >= minsum:\n",
    "                    return True\n",
    "            return False\n",
    "        while j-i > 0.000001:\n",
    "            m = (j+i)/2\n",
    "            if check(m, k):\n",
    "                i = m\n",
    "            else:\n",
    "                j = m\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        def check(mid):\n",
    "            s, pre, mn = 0, 0, 0\n",
    "            for i, x in enumerate(nums[:k]):\n",
    "                s += x - mid\n",
    "            if s >= 0: return True\n",
    "            for i in range(k, n):\n",
    "                s += nums[i] - mid\n",
    "                pre += nums[i - k] - mid\n",
    "                mn = min(mn, pre)\n",
    "                if s >= mn:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        l, r = min(nums), max(nums)\n",
    "        while r - l > 1e-5:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        stack = deque()\n",
    "        st = 0\n",
    "        N = len(nums)\n",
    "        for i in range(0, k):\n",
    "            st += nums[i]\n",
    "        ans = st / k\n",
    "        ct = k\n",
    "        for i in range(1, N - k + 1):\n",
    "            st += nums[i + k - 1]\n",
    "            ct += 1\n",
    "            s1 = nums[i - 1]\n",
    "            c1 = 1\n",
    "            # S0 / C0 >= S1 / C1\n",
    "            while stack and stack[-1][1] * c1 >= s1 * stack[-1][0]:\n",
    "                c0, s0 = stack.pop()\n",
    "                c1 += c0\n",
    "                s1 += s0\n",
    "            stack.append((c1, s1))\n",
    "            # S0 / C0 <= st / ct\n",
    "            while stack and stack[0][1] * ct <= st * stack[0][0]:\n",
    "                c0, s0 = stack.popleft()\n",
    "                ct -= c0\n",
    "                st -= s0\n",
    "            ans = max(ans, st / ct)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        def check(v: float) -> bool:\n",
    "            s = sum(nums[:k]) - k * v\n",
    "            if s >= 0:\n",
    "                return True\n",
    "            t = mi = 0\n",
    "            for i in range(k, len(nums)):\n",
    "                s += nums[i] -v\n",
    "                t += nums[i - k] - v\n",
    "                mi = min(mi, t)\n",
    "                if s >= mi:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        eps = 1e-5\n",
    "        l, r = min(nums), max(nums)\n",
    "        while r - l >= eps:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # (count, sum)\n",
    "        stack = deque()\n",
    "        st = 0\n",
    "        N = len(nums)\n",
    "        for i in range(0, k):\n",
    "            st += nums[i]\n",
    "        ans = st / k\n",
    "        ct = k\n",
    "        for i in range(1, N - k + 1):\n",
    "            st += nums[i + k - 1]\n",
    "            ct += 1\n",
    "            s1 = nums[i - 1]\n",
    "            c1 = 1\n",
    "            # S0 / C0 >= S1 / C1\n",
    "            while stack and stack[-1][1] * c1 >= s1 * stack[-1][0]:\n",
    "                c0, s0 = stack.pop()\n",
    "                c1 += c0\n",
    "                s1 += s0\n",
    "            stack.append((c1, s1))\n",
    "            # S0 / C0 <= st / ct\n",
    "            while stack and stack[0][1] * ct <= st * stack[0][0]:\n",
    "                c0, s0 = stack.popleft()\n",
    "                ct -= c0\n",
    "                st -= s0\n",
    "            ans = max(ans, st / ct)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # (count, sum)\n",
    "        stack = deque()\n",
    "        st = 0\n",
    "        N = len(nums)\n",
    "        for i in range(0, k):\n",
    "            st += nums[i]\n",
    "        ans = st / k\n",
    "        ct = k\n",
    "        for i in range(1, N - k + 1):\n",
    "            st += nums[i + k - 1]\n",
    "            ct += 1\n",
    "            s1 = nums[i - 1]\n",
    "            c1 = 1\n",
    "            # S0 / C0 >= S1 / C1\n",
    "            while stack and stack[-1][1] * c1 >= s1 * stack[-1][0]:\n",
    "                c0, s0 = stack.pop()\n",
    "                c1 += c0\n",
    "                s1 += s0\n",
    "            stack.append((c1, s1))\n",
    "            # S0 / C0 <= st / ct\n",
    "            while stack and stack[0][1] * ct <= st * stack[0][0]:\n",
    "                c0, s0 = stack.popleft()\n",
    "                ct -= c0\n",
    "                st -= s0\n",
    "            ans = max(ans, st / ct)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l,r = min(nums),max(nums)\n",
    "        def ok(x):\n",
    "            ss1=0\n",
    "            ss0=0\n",
    "            mss0=inf\n",
    "            for i,c in enumerate(nums):\n",
    "                ss1+=c-x\n",
    "                if i-k>=0: \n",
    "                    ss0+=nums[i-k]-x\n",
    "                if i+1>=k:\n",
    "                    mss0=min(mss0, ss0)\n",
    "                    if ss1>=mss0: return True\n",
    "            return False\n",
    "                    \n",
    "        while abs(r-l)>pow(10,-5):\n",
    "            x=l+(r-l)/2\n",
    "            if ok(x):\n",
    "                l=x\n",
    "            else:\n",
    "                r=x\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float: \n",
    "        def check(avg):\n",
    "            # 如果是求长度等于 k 的区间的区间和：\n",
    "            # 使用滑动窗口，维护首尾前缀和（见643.最大平均子段和）\n",
    "            # 这一题是大于等于 k\n",
    "            # 我们需要知道以 end 结尾，长度大于等于 k 的区间中最大的区间和\n",
    "            # 多维护一个 start_sum 的最小值即可\n",
    "            # end_sum - min_sum 即为所求区间和最大值 \n",
    "            end_sum = sum(num - avg for num in nums[:k])\n",
    "            start_sum = min_start_sum = 0\n",
    "            for end in range(k, len(nums)):\n",
    "                if end_sum >= min_start_sum:\n",
    "                    return True\n",
    "                end_sum += nums[end] - avg\n",
    "                start_sum += nums[end-k] - avg\n",
    "                min_start_sum = min(min_start_sum, start_sum)\n",
    "            return end_sum >= min_start_sum \n",
    "        # 二分法\n",
    "        l, r = min(nums), max(nums)\n",
    "        while r - l > 1e-5:\n",
    "            mid = (l+r) / 2\n",
    "            if check(mid):  # 存在符合条件的区间，其平均值大于等于 mid，下界向上收缩\n",
    "                l = mid \n",
    "            else:\n",
    "                r = mid \n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        # 答案误差不超过1e-5是使用二分搜索的提示，可以先确定最大平均值的范围一定在数组的最大元素和最小元素之间，然后在该区间内用二分搜索，对于每个值检查是否能找到满足平均值大于该值且长度>=k的子数组，逐步缩小最大平均值的范围，直到误差小于1e-5。对于给定一个值guess_avg找出原数组是否含有满足平均值大于该值且长度>=k的子数组的子问题，类似于滑动窗口，用 max_sum 记录前i个元素之和减去i * guess_avg的值，用min_start_sum记录某个连续子数组最小平均值, 这样若 max_sum - min_start_sum>=0则表示存在满足条件的子数组. \n",
    "        def check(guess_avg):\n",
    "            # 记录从nums[0]开始，长度>=k的平均值\n",
    "            max_sum = 0\n",
    "            for num in nums[:k]:\n",
    "                max_sum += num - guess_avg\n",
    "            # 记录遍历中nums[0:i]的平均值 （通过计算每个元素 - guess_avg后的累计和得到）\n",
    "            curr_sum = 0\n",
    "            # 记录遍历中nums[0:i]的某个连续子数组最小平均值\n",
    "            min_start_sum = 0\n",
    "            for i in range(k, len(nums)):\n",
    "                # 因为max_sum从k开始遍历，能够保证max_sum - min_start_sum始终对应某个长度>=k的连续子数组\n",
    "                # 这里分析min_start_sum初始化0的影响。如果min_start_sum是负数，代表着nums靠前部分存在大量平均值<guess_avg的小数字，则max_sum - min_start_sum相当于某个子数组能够甩掉前面小数字的包袱，达到平均值>=guess_avg\n",
    "                # 第二种情况min_start_sum继续为0。因为max_sum = sum(nums[:i]) - i * guess_avg, 正好说明avg(nums[:i])>=guess_avg，满足条件。\n",
    "                if max_sum - min_start_sum >= 0:\n",
    "                    return True\n",
    "                max_sum += nums[i] - guess_avg\n",
    "                curr_sum += nums[i - k] - guess_avg\n",
    "                min_start_sum = min(min_start_sum, curr_sum)\n",
    "            return max_sum - min_start_sum >= 0\n",
    "        \n",
    "        # 题目给出的元素范围\n",
    "        left, right = -10001, 10001\n",
    "        while right - left > 1e-5:\n",
    "            guess_avg = left + (right - left) / 2\n",
    "            if check(guess_avg): \n",
    "                # 存在符合条件的区间，其平均值>=guess_avg，下界向上收缩\n",
    "                # 由于这个题为double类型，分为[left, mid]和[mid, right]\n",
    "                left = guess_avg\n",
    "            else:\n",
    "                right = guess_avg\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        def check(avg):\n",
    "            end_sum = sum(num-avg for num in nums[:k])\n",
    "            start_sum = min_start = 0\n",
    "            for end in range(k, n):\n",
    "                if end_sum >= min_start:\n",
    "                    return True\n",
    "\n",
    "                end_sum += nums[end]-avg\n",
    "                start_sum += nums[end-k]-avg\n",
    "                min_start = min(min_start, start_sum)\n",
    "            return end_sum >= min_start\n",
    "        \n",
    "        left, right = min(nums), max(nums)\n",
    "        while right - left > 1e-5:\n",
    "            mid = (left + right) / 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "            # print(left, right)\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        def check(nums,mid,k):\n",
    "            prev_sum,min_sum=0,0\n",
    "            total_sum=0\n",
    "            for i in range(k):\n",
    "                total_sum+=nums[i]-mid\n",
    "            if total_sum>=0:\n",
    "                return True\n",
    "            for i in range(k,len(nums)):\n",
    "                total_sum+=nums[i]-mid\n",
    "                prev_sum+=nums[i-k]-mid\n",
    "                min_sum=min(min_sum,prev_sum)\n",
    "                if total_sum>=min_sum:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        min_val=min(nums)\n",
    "        max_val=max(nums)\n",
    "        l,r=min_val,max_val\n",
    "        prev_mid=max_val\n",
    "        error=max_val\n",
    "        while error>0.00001:\n",
    "            mid=(l+r)/2\n",
    "            if check(nums,mid,k):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "            error=abs(prev_mid-mid)\n",
    "            prev_mid=mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        #前缀和+二分\n",
    "        def check(mid):\n",
    "            pre1,pre2,mpre=0,0,inf\n",
    "            for i in range(n):\n",
    "                pre1+=nums[i]-mid\n",
    "                #可以更新超前缀和\n",
    "                if i-k>=0:\n",
    "                    pre2+=nums[i-k]-mid\n",
    "                #这步更新很精髓\n",
    "                if i+1>=k:\n",
    "                    mpre=min(mpre,pre2)\n",
    "                    if pre1-mpre>=0:\n",
    "                        return True\n",
    "            return False\n",
    "        left,right=min(nums),max(nums)\n",
    "        n=len(nums)\n",
    "        while right-left>pow(10,-5):\n",
    "            mid=(left+right)/2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l,r = min(nums),max(nums)\n",
    "        def ok(x):\n",
    "            ss1=0\n",
    "            ss0=0\n",
    "            mss0=inf\n",
    "            for i,c in enumerate(nums):\n",
    "                ss1+=c-x\n",
    "                if i-k>=0: \n",
    "                    ss0+=nums[i-k]-x\n",
    "                if i+1>=k:\n",
    "                    mss0=min(mss0, ss0)\n",
    "                    if ss1>=mss0: return True\n",
    "            return False\n",
    "                    \n",
    "        while abs(r-l)>pow(10,-5):\n",
    "            x=l+(r-l)/2\n",
    "            if ok(x):\n",
    "                l=x\n",
    "            else:\n",
    "                r=x\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "ERROR = 1e-5\n",
    "\n",
    "def pre_sum_without_avg(nums, avg):\n",
    "    presum = [0]*(len(nums)+1)\n",
    "    for i in range(len(nums)):\n",
    "        presum[i+1] = presum[i]+nums[i]-avg\n",
    "    return presum\n",
    "\n",
    "def pre_min(presum):\n",
    "    premin = [0]*len(presum)\n",
    "    for i in range(1, len(presum)):\n",
    "        premin[i] = min(premin[i-1], presum[i])\n",
    "    return premin\n",
    "\n",
    "def exist_above_avg(nums, avg, k):\n",
    "    presum = pre_sum_without_avg(nums, avg)\n",
    "    premin = pre_min(presum)\n",
    "    for i in range(k, len(presum)):\n",
    "        if presum[i] - premin[i-k] >= 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def bisect(check, left, right):\n",
    "    while right-left > ERROR:\n",
    "        mid = (left + right) / 2\n",
    "        if check(mid):\n",
    "            right = mid\n",
    "        else: \n",
    "            left = mid\n",
    "    return (left+right)/2\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        \"\"\"\n",
    "        (a1+a2+a3+a4)/l >= avg\n",
    "        (a1-avg)+(a2-avg)+(a3-avg)+(a4-avg) >= 0\n",
    "        \"\"\"\n",
    "        left, right = min(nums), max(nums)+ERROR\n",
    "        check = lambda x: exist_above_avg(nums, x, k)\n",
    "        left = bisect(check, left, right)\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l,r = min(nums),max(nums)\n",
    "        def ok(x):\n",
    "            ss1=0\n",
    "            ss0=0\n",
    "            mss0=inf\n",
    "            for i,c in enumerate(nums):\n",
    "                ss1+=c-x\n",
    "                if i-k>=0: \n",
    "                    ss0+=nums[i-k]-x\n",
    "                if i+1>=k:\n",
    "                    mss0=min(mss0, ss0)\n",
    "                    if ss1>=mss0: return True\n",
    "            return False\n",
    "                    \n",
    "        while abs(r-l)>pow(10,-5):\n",
    "            x=l+(r-l)/2\n",
    "            if ok(x):\n",
    "                l=x\n",
    "            else:\n",
    "                r=x\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l = min(nums)\n",
    "        r = max(nums)\n",
    "        def check(target):\n",
    "            presum = 0\n",
    "            premin = 0\n",
    "            s = 0\n",
    "            for i in range(len(nums)):\n",
    "                s += nums[i] - target \n",
    "                if i >= k - 1:\n",
    "                    if s - premin >= 0:\n",
    "                        return True \n",
    "                    presum += nums[i - k + 1] - target\n",
    "                    premin = min(premin, presum)\n",
    "            return False \n",
    "\n",
    "        while l + 1e-9 < r:\n",
    "            mid = l + (r - l) / 2 \n",
    "            if not check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        #前缀和+二分\n",
    "        def check(mid):\n",
    "            pre1,pre2,mpre=0,0,inf\n",
    "            for i in range(n):\n",
    "                pre1+=nums[i]-mid\n",
    "                #可以更新超前缀和\n",
    "                if i-k>=0:\n",
    "                    pre2+=nums[i-k]-mid\n",
    "                if i+1>=k:\n",
    "                    mpre=min(mpre,pre2)\n",
    "                    if pre1-mpre>=0:\n",
    "                        return True\n",
    "            return False\n",
    "        left,right=min(nums),max(nums)\n",
    "        n=len(nums)\n",
    "        while right-left>pow(10,-5):\n",
    "            mid=(left+right)/2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        #前缀和+二分\n",
    "        def check(mid):\n",
    "            pre1,pre2,mpre=0,0,inf\n",
    "            for i in range(n):\n",
    "                pre1+=nums[i]-mid\n",
    "                #可以更新超前缀和\n",
    "                if i-k>=0:\n",
    "                    pre2+=nums[i-k]-mid\n",
    "                if i+1>=k:\n",
    "                    mpre=min(mpre,pre2)\n",
    "                    if pre1-mpre>=0:\n",
    "                        return True\n",
    "            return False\n",
    "        left,right=min(nums),max(nums)\n",
    "        n=len(nums)\n",
    "        while right-left>pow(10,-5):\n",
    "            mid=(left+right)/2\n",
    "            if check(mid):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        def check(x):\n",
    "            end_sum = sum(num - x for num in nums[:k])\n",
    "            start_sum = min_start_sum = 0\n",
    "            for end in range(k, len(nums)):\n",
    "                if end_sum >= min_start_sum:\n",
    "                    return True\n",
    "                end_sum += nums[end] - x\n",
    "                start_sum += nums[end - k] - x\n",
    "                min_start_sum = min(min_start_sum, start_sum)\n",
    "            return end_sum >= min_start_sum\n",
    "        \n",
    "        l, r = min(nums), max(nums)\n",
    "        while r - l > 1e-5:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        l,r = min(nums),max(nums)\n",
    "\n",
    "        def check(mid):\n",
    "            s,pre,mn = sum(x - mid for x in nums[:k]),0,0\n",
    "            if s >= 0:\n",
    "                return True\n",
    "            for i in range(k,n):\n",
    "                s += nums[i] - mid\n",
    "                pre += nums[i - k] - mid\n",
    "                mn = min(mn,pre)\n",
    "                if s >= mn:\n",
    "                    return True\n",
    "            return False\n",
    "            \n",
    "\n",
    "        while r - l > 1e-5:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l = min(nums)\n",
    "        r = max(nums)\n",
    "        def check(target):\n",
    "            presum = 0\n",
    "            premin = 0\n",
    "            s = 0\n",
    "            for i in range(len(nums)):\n",
    "                s += nums[i] - target \n",
    "                if i >= k - 1:\n",
    "                    if s - premin >= 0:\n",
    "                        return True \n",
    "                    presum += nums[i - k + 1] - target\n",
    "                    premin = min(premin, presum)\n",
    "            return False \n",
    "\n",
    "        while l + 1e-9 < r:\n",
    "            mid = l + (r - l) / 2 \n",
    "            if not check(mid):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid \n",
    "        return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        l,r = min(nums),max(nums)\n",
    "        def ok(x):\n",
    "            ss1=0\n",
    "            ss0=0\n",
    "            mss0=inf\n",
    "            for i,c in enumerate(nums):\n",
    "                ss1+=c-x\n",
    "                if i-k>=0: \n",
    "                    ss0+=nums[i-k]-x\n",
    "                if i+1>=k:\n",
    "                    mss0=min(mss0, ss0)\n",
    "                    if ss1>=mss0: return True\n",
    "            return False\n",
    "                    \n",
    "        while abs(r-l)>pow(10,-5):\n",
    "            x=l+(r-l)/2\n",
    "            if ok(x):\n",
    "                l=x\n",
    "            else:\n",
    "                r=x\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "\n",
    "        def max_avg(k):\n",
    "            max_sum = -sys.maxsize\n",
    "            s = sum(nums[:k - 1])\n",
    "            for i in range(k - 1, n):\n",
    "                s += nums[i]\n",
    "                max_sum = max(max_sum, s)\n",
    "                s -= nums[i - k + 1]\n",
    "            return max_sum / k\n",
    "\n",
    "        def is_avg_gte(j):\n",
    "            min_pre = 0\n",
    "            pre = 0\n",
    "            s = sum(nums[:k - 1]) - (k - 1) * j\n",
    "            for i in range(k - 1, n):\n",
    "                s += nums[i] - j\n",
    "                if s >= min_pre:\n",
    "                    return True\n",
    "                pre += nums[i - k + 1] - j \n",
    "                min_pre = min(min_pre, pre)\n",
    "            return False\n",
    "\n",
    "        l, r = min(nums), max(nums)\n",
    "        while l + 0.00001 <= r:\n",
    "            mid = (l + r) / 2\n",
    "            # mid = 7\n",
    "            if is_avg_gte(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        def check(avg):\n",
    "            end_sum = sum(num - avg for num in nums[:k])\n",
    "            start_sum = min_start_sum = 0\n",
    "            for end in range(k, len(nums)):\n",
    "                if end_sum >= min_start_sum:\n",
    "                    return True\n",
    "                end_sum += nums[end] - avg\n",
    "                start_sum += nums[end - k] - avg\n",
    "                min_start_sum = min(min_start_sum, start_sum)\n",
    "            return end_sum >= min_start_sum\n",
    "\n",
    "        left, right = min(nums), max(nums)\n",
    "        while right - left > 1e-5:\n",
    "            mid = (left + right) / 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        stack = deque()\n",
    "        st = 0\n",
    "        N = len(nums)\n",
    "        for i in range(0, k):\n",
    "            st += nums[i]\n",
    "        ans = st / k\n",
    "        ct = k\n",
    "        for i in range(1, N - k + 1):\n",
    "            st += nums[i + k - 1]\n",
    "            ct += 1\n",
    "            s1 = nums[i - 1]\n",
    "            c1 = 1\n",
    "            while stack and stack[-1][1] * c1 >= s1 * stack[-1][0]:\n",
    "                c0, s0 = stack.pop()\n",
    "                c1 += c0\n",
    "                s1 += s0 \n",
    "            stack.append((c1, s1))\n",
    "            while stack and stack[0][1] * ct <= st * stack[0][0]:\n",
    "                c0, s0 = stack.popleft()\n",
    "                ct -= c0 \n",
    "                st -= s0 \n",
    "            ans = max(ans, st /ct)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        _max, _min = float('-inf'), float('inf')\n",
    "        for num in nums:\n",
    "            _max = max(_max, num)\n",
    "            _min = min(_min, num)\n",
    "        l, r = _min, _max\n",
    "        while l < r - 0.00001:\n",
    "            m = (l + r) / 2\n",
    "            if self.check(nums, k, m):\n",
    "                l = m + 0.00001\n",
    "            else:\n",
    "                r = m - 0.00001\n",
    "        return r\n",
    "    \n",
    "    def check(self, nums, k, avg):\n",
    "        n = len(nums)\n",
    "        # 判断均值是否大于目标值，涉及总和与总个数，不便于动态窗口处理\n",
    "        # 令各值都减去目标值，根据累加和的正负即可判断均值是否大于目标值（数学技巧）\n",
    "        lst = [num - avg for num in nums]\n",
    "        # 前k个的和rsum大于等于0直接返回True\n",
    "        rsum = 0\n",
    "        for i in range(k):\n",
    "            rsum += lst[i]\n",
    "        if rsum >= 0:\n",
    "            return True\n",
    "        # 依次判断各个结束位置i，若（该位置累加和 - k个位置前的最小累加和prev）>= 0，则返回True\n",
    "        lsum, prev_min_sum = 0, 0\n",
    "        for i in range(k, n):\n",
    "            lsum += lst[i - k]\n",
    "            rsum += lst[i]\n",
    "            prev_min_sum = min(prev_min_sum, lsum)\n",
    "            if rsum - prev_min_sum >= 0:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "\n",
    "        def is_avg_gte(j):\n",
    "            '''\n",
    "            关键是这个函数的实现：nums 中的每个数都减去 j，那么问题就可以转化为：\n",
    "            是否存在某个子数组的和大于 0。只要不停计算前缀和然后相减就好了，不需要考虑字数组长度\n",
    "            '''\n",
    "            min_pre = 0\n",
    "            pre = 0\n",
    "            s = sum(nums[:k - 1]) - (k - 1) * j\n",
    "            for i in range(k - 1, n):\n",
    "                s += nums[i] - j\n",
    "                if s >= min_pre:\n",
    "                    return True\n",
    "                pre += nums[i - k + 1] - j \n",
    "                min_pre = min(min_pre, pre)\n",
    "            return False\n",
    "\n",
    "        l, r = min(nums), max(nums)\n",
    "        while l + 0.00001 <= r:\n",
    "            mid = (l + r) / 2\n",
    "            # mid = 7\n",
    "            if is_avg_gte(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        def check(_):\n",
    "            a = [float(x) - _ for x in nums]\n",
    "            pre_min = float('inf')\n",
    "            pres = list(accumulate(a, initial=0.0))\n",
    "            for i in range(k, len(pres)):\n",
    "                pre_min = min(pre_min, pres[i - k])\n",
    "                if pres[i] >= pre_min:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        l = -1e5\n",
    "        r = 1e5\n",
    "\n",
    "        while r - l > 1e-8:\n",
    "            mid = (l + r) / 2\n",
    "            if check(mid): l = mid\n",
    "            else: r = mid\n",
    "        return r                 \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        _max, _min = float('-inf'), float('inf')\n",
    "        for num in nums:\n",
    "            _max = max(_max, num)\n",
    "            _min = min(_min, num)\n",
    "        l, r = _min, _max\n",
    "        while l < r - 0.00001:\n",
    "            m = (l + r) / 2\n",
    "            if self.check(nums, k, m):\n",
    "                l = m + 0.00001\n",
    "            else:\n",
    "                r = m - 0.00001\n",
    "        return r\n",
    "    \n",
    "    def check(self, nums, k, avg):\n",
    "        n = len(nums)\n",
    "        # 判断均值是否大于目标值，涉及总和与总个数，不便于动态窗口处理\n",
    "        # 令各值都减去目标值，根据累加和的正负即可判断均值是否大于目标值（数学技巧）\n",
    "        arr = [num - avg for num in nums]\n",
    "        # 计算从左至右的累加和数组\n",
    "        csum = [0] * n\n",
    "        csum[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            csum[i] = csum[i - 1] + arr[i]\n",
    "        # 计算从某个位置至结束范围内，累加和数组的最大值\n",
    "        rmax = [0] * n\n",
    "        rmax[-1] = csum[-1]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            rmax[i] = max(rmax[i + 1], csum[i])\n",
    "        # 根据各个起始位置判断最大累加和是否满足要求\n",
    "        if rmax[k - 1] >= 0:\n",
    "            return True\n",
    "        for i in range(1, n - k + 1):\n",
    "            if rmax[i + k - 1] - csum[i - 1] >= 0:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaxAverage(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        def check(mid):\n",
    "            pre=[0]+list(accumulate([v-mid for v in nums]))\n",
    "            minv=0\n",
    "            for i in range(k,n+1):\n",
    "                # 这里不能pre[i]-pre[i-k]>=0\n",
    "                # [-1,2,-3,-2,3]\n",
    "                if pre[i]-minv>=0:\n",
    "                    return True\n",
    "                # 必须保持距离大于等于k\n",
    "                minv = min(minv,pre[i-k+1]) \n",
    "            return False\n",
    "\n",
    "        l,r=min(nums),max(nums)\n",
    "        # 二分\n",
    "        while r-l>1e-5:\n",
    "            mid=(l+r)/2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        return r\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
